In general, autonomous systems (AS) having networks under a common administrator may share a common routing policy for communication therebetween, such as border gateway protocol (BGP). Within each autonomous system, the routing protocol typically entails an interior gateway protocol (IGP), such as a link state protocol.
Link state protocol generally relies on a routing algorithm executed at each network node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link, which can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in a first direction along a link may be different from the cost in a second, reverse direction. Based on the advertised information in the form of a link state packet (LSP) each node constructs a link state database (LSDB), which is a map of the entire network topology, and from that constructs generally a single route to each available node based on an appropriate algorithm such as, a shortest path first (SPF) algorithm. As a result, a spanning tree is constructed, rooted at the node and showing a communication path including intermediate nodes to each available destination node.
The results of the spanning tree can be stored in a routing information base (RIB) and based on these results the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately. When there is a network change a link state packet representing the change is flooded through the network by each node adjacent the change, each node receiving the link state packet sends it to each adjacent node. As a result, when a data packet for a destination node arrives at a node the node identifies a route to that destination and forwards the packet to the next node along that route. The next node repeats this step and so forth.